package real.meituan;

import list.ListNode;

/**
 * 反转链表
 */
public class ReserveList {
    //给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
    //要求：空间复杂度
    //O(1) ，
    //时间复杂度
    //O(n) 。
    //
    //如当输入链表{1,2,3}时，
    //经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}

    public ListNode reserveList(ListNode head){
        if(head == null){
            return head;
        }
        ListNode node = head;
        ListNode realNext = head.next;
        node.next = null;
        while (realNext != null){
            ListNode next1 = realNext.next;
            realNext.next = node;
            node = realNext;
            realNext = next1;
        }
        return node;
    }


    public static void main(String[] args) {
        ReserveList rl = new ReserveList();

        // 测试用例1：链表{1,2,3}
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        ListNode reversed1 = rl.reserveList(head1);
        printList(reversed1); // 预期输出：3 2 1

        // 测试用例2：链表{1}
        ListNode head2 = new ListNode(1);
        ListNode reversed2 = rl.reserveList(head2);
        printList(reversed2); // 预期输出：1

        // 测试用例3：空链表
        ListNode reversed3 = rl.reserveList(null);
        printList(reversed3); // 预期输出：（无输出）
    }

    // 辅助方法：打印链表
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

}
